import java.util.*;

/**
 * @Author: Darven
 * @CreateTime: 2025-04-01  19:05
 * @Description: 17. 电话号码的字母组合
 */
public class P17 {
    public static void main(String[] args) {
        P17Demo p17Demo = new P17Demo();
        System.out.println(p17Demo.letterCombinations("23").toString());
    }
}

class P17Demo{
    public List<String> letterCombinations(String digits) {
        if (digits.equals("")) {
            return new ArrayList<String>();
        } else if (digits == null) {
            return new ArrayList<String>();
        }
        String[] s={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        List<String> ans=new ArrayList<>();
        StringBuffer sb=new StringBuffer();
        back(ans, digits, sb,s,0);

        return ans;
    }

    public void back(List<String> ans, String digits,StringBuffer sb,String[] s,int deep){

        if(deep==digits.length()){
            ans.add(sb.toString());
            return ;
        }

        for(int i=0;i<s[digits.charAt(deep)-'2'].length();i++){
            sb.append(s[digits.charAt(deep)-'2'].charAt(i));
            back(ans,digits, sb, s,deep+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans=new ArrayList<>();
        List<Integer> read= new ArrayList<>();
        List<Integer> tmp=new ArrayList<>();
        for(int i:nums){
            read.add(i);
        }
        dfs(0, nums, tmp, ans, read);
        return ans;
    }

    public void dfs(int index,int[] nums,List<Integer> tmp,List<List<Integer>> ans,List<Integer> read){
        if(index==nums.length){
            ans.add(tmp);
            return ;
        }
        for(int i=0;i<read.size();i++){
            tmp.add(read.get(i));
            List<Integer> list = new ArrayList<>(read);
            list.remove(read.get(i));
            dfs(index+1,nums,tmp,ans,list);
            tmp.removeLast();
        }
    }
}
